<!DOCTYPE doctype PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<html><head>


  <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  <meta http-equiv="Content-Language" content="es-ar">
  <meta name="GENERATOR" content="A mano lo que venga">
  <meta name="Author" content="Nicolas Wolovick">
  <meta name="keywords" content="manejo memoria politica mecanismo memory management policy mecanism trace malloc sistemas operativos FaMAF educacion education operating systems linux">
  <style type="text/css">
	H1, H2, H3, DIV, P, LI,
	UL, OL, TABLE, TD, TR {font-family: lucida sans, helvetica, arial, sans-serif;}
	pre {background: #eee; border: 1px dashed #889; margin-left: 3em; padding: 1ex;}
	dt {font-family: monospace; font-weight: bold;}
  </style><title>Lab4: Administración de Memoria</title></head><body>

<!--============================================================-->
<h1>Lab4: Administración de Memoria</h1>
<h3>Nicolás Wolovick, Matías Cuenca-Acuña</h3>

<!--============================================================-->
<h1>Objetivos</h1>
<ul>
	<li>Implementar diferentes algoritmos para administrar recursos.</li>
	<li>Comprender la importancia de definir políticas adecuadas a los casos de uso.</li>
	<li>Aplicar la técnica de programación: política vs. mecanismo.</li>
	<li>Brindar
un banco de pruebas que permita, mediante trazas extraídas de
aplicaciones reales, probar diferentes políticas de ubicación de
memoria.</li>
</ul>

<p>
</p><h1>Introducción</h1>

<p>
Una de las funciones básicas de un Sistema Operativo es el <b>manejo de recursos</b>.
<br>
Como tal, el SO tiene que implementar algoritmos correctos y rápidos, a
fin de obtener el máximo provecho a los recursos que son materialmente
caros, como por ejemplo la memoria.
</p><p>
En la mayoría de los casos estos algoritmos dependen mucho del <i>patrón de uso</i> que los procesos hacen del recurso y las <i>tecnologías involucradas</i>.

</p><p>
Un ejemplo típico dentro de los File Systems en disco, es el caso de los archivos pequeños.
<br>Una rápida inspección de un sistema de archivos tipo UNIX muestra que más del 70% de los archivos tienen menos de 4KB.
Luego, es de esperar que los algoritmos y estructuras de datos de un file system como <a href="http://en.wikipedia.org/wiki/Ext3">ext3</a> o <a href="http://oss.sgi.com/projects/xfs/">XFS</a> estén optimizados para este caso tan frecuente.
Si el patrón de uso no se presenta de esa forma, probablemente los algoritmos y estructuras de datos se comporten pobremente.

</p><p>
</p><blockquote>
<table><tbody><tr><td bgcolor="#c0c0c0">No hay mejores algoritmos y
estructuras de datos en sentido absoluto, cada uno tiene su debilidades
y fortalezas, sin embargo en los casos más probables funcionan de
manera óptima.
<br>Es tarea de un implementador de SO medir y comprender los patrones
de uso de los recursos para luego implementar algoritmos adecuados y
medir su eficiencia.
</td></tr></tbody></table>
</blockquote>


<!---------------------------------------------------------------->
<h2>Administrador de bloques contiguos de memoria</h2>

<p>
Un ejemplo de administración de recursos es un <i>heap manager</i>, es decir el conjunto de algoritmos y estructuras de datos que manejan las llamadas a biblioteca
<tt><a href="http://www.gnu.org/software/libc/manual/html_node/Basic-Allocation.html">malloc</a></tt>,
<tt><a href="http://www.gnu.org/software/libc/manual/html_node/Changing-Block-Size.html">realloc</a></tt> y
<tt><a href="http://www.gnu.org/software/libc/manual/html_node/Freeing-after-Malloc.html">free</a></tt>,
que piden y devuelven memoria para los programas de usuario.

</p><p>
Podemos dar una descripción operacional de lo que hacen estas llamadas.
<br>
Dado un espacio de memoria contiguo en el <i>data segment</i> (DS) pedido al kernel con la syscall <tt><a href="http://www.gnu.org/software/libc/manual/html_node/Resizing-the-Data-Segment.html">brk</a></tt>, el heap manager tiene que:
</p><ul>
	<li><tt>address = malloc(size)</tt>: devolver una dirección de memoria <tt>address</tt> dentro de ese segmento de datos que tenga al menos <tt>size</tt> bytes libres a partir de la dirección.</li>
	<li><tt>address = realloc(address, new_size)</tt>: si a continuación del bloque ocupado desde <tt>address</tt> hay lugar para agrandarlo (o achicarlo!?) a <tt>new_size</tt>, entonces mueve la marca que indica el fin de esa región asociada a <tt>address</tt>.</li>
	<li><tt>free(address)</tt>: libera toda la memoria que tiene asignada <tt>address</tt>.</li>
</ul>

<p>
Si pensamos un poco en lo que sucede internamente, el heap manager (HM) tiene que <b>llevar cuenta</b>
de que partes del DS están ocupadas y libres para no asignar 2 veces la
misma memoria, así como tener en cuenta el tamaño asociado a cada
puntero devuelto por <tt>malloc</tt> a fin de poder liberar la cantidad correcta de memoria <tt>free(address)</tt> o bien poder cambiar su tamaño <tt>realloc(address,size)</tt>.

</p><p>
También notamos que la <tt>libc</tt> tiene que tomar decisiones respecto a donde colocar un nuevo bloque de datos.
<br>
Luego de un tiempo de uso, es esperable que el DS se <b>fragmente externamente</b> como en la siguiente figura, donde hay unidades <font color="#99cccc">libres</font> y unidades <font color="#cc2020">ocupadas</font>:

</p><p>
<table border="1" cellpadding="1" cellspacing="1">
	<tbody><tr>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#cc2020">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
		<td bgcolor="#99cccc">&nbsp;&nbsp;&nbsp;&nbsp;</td>
	</tr>
</tbody></table>
</p><p>
¿Qué hacer si llega un pedido por 3 unidades de memoria?
Tenemos al menos 4 opciones:
</p><ul>
	<li>Colocarlo en el bloque de 7 libres.</li>
	<li>Colocarlo en el siguiente de 5 libres.</li>
	<li>Ubicarlo al final donde entra justo.</li>
	<li>Decir que no hay memoria devolviendo <tt>NULL</tt>.</li>
</ul>

<p>
Notar que la cuarta es una opción válida, aunque obtiene muy poco provecho del recurso (algo asi como <i>false</i> implica cualquier cosa, sencillo pero inútil).
<br>
Entre las 3 opciones restantes tenemos que decidir de manera adecuada una <b>política de ubicación</b> a fin de que el recurso memoria sea eficientemente utilizado.
Parecería que lo ideal es colocarlo en el último bloque, ya que entra justo, pero ... ¿Y si inmediatamente después tenemos un <tt>realloc</tt> que aumenta el tamaño?
<br>
El problema tiene muchos más casos para analizar, pero con este ejemplo mostramos que el algoritmo <i>best-fit</i> no siempre es el más conveniente.

</p><p>
Es importante remarcar que independientemente de la política utilizada,
muchas estructuras de datos y algoritmos permanecen inalterados, como
por ejemplo llevar registro de las celdas libres o de los tamaños de
bloque asignados a cada dirección.
<br>
Usualmente se denomina a estas partes más estáticas como <b>mecanismos</b>.

</p><p>
Un caso típico de división entre política y mecanismo está en las interfaces gráficas de UNIX.
<br> El servidor X solo implementa mecanismos, son motores de dibujo;
mientras que los administradores de ventana implementan políticas, como
el look&amp;feel.
<br> En <a href="http://www.catb.org/%7Eesr/writings/taoup/html/ch01s06.html#id2877777">The Art of UNIX Programming, Chapter 1. Philosophy</a>, Eric Raymond explica:
</p><blockquote><i> Nosotros justificamos esto [dividir política de
mecanismo] haciendo notar que la política y el mecanismo tienden a
cambiar en escalas temporales diferentes, donde la política cambia
mucho más rápido que el mecanismo.
</i></blockquote>

<!---------------------------------------------------------------->
<h2>Ejercicios</h2>
<ul>
	<li>¿ Qué sucede si se hace un <tt>free</tt> de una dirección que no fue devuelta por <tt>malloc</tt>/<tt>realloc</tt> como en el siguiente programa?
	<br>
	<pre width="50">ptr = malloc(256);
free(ptr+1);
	</pre>
	</li>
	<li>Investigue la <i>semántica</i> de <tt>realloc(NULL, size)</tt> y <tt>realloc(address,0)</tt>, asi como de un <tt>realloc</tt> por un tamaño menor al original.</li>
	<li>Piense en las estructuras de datos necesarias para mantener la información acerca de los pedazos de memoria ocupados y libres.</li>
	<li>¿Qué sucede cuando no hay espacio contiguo para hacer el <tt>realloc</tt>?</li>
	<li>¿Qué haría como programador de la <tt>libc</tt>
para evitar relocalizar bloques de memoria cada vez que se aumenta un
poco la cantidad de memoria? Piense en un programa como el siguiente: <br>
	<pre width="50">ptr=NULL;
for(i=1; i&lt;131072; i++)
	ptr = realloc(ptr, i);
	</pre>
	</li>
	<li>¿Qué tamaños tienen las llamadas <tt>malloc</tt> de un proceso como por ejemplo Firefox?
	¿Cuál es su patrón?
	¿Cómo las obtendría?
	</li>
</ul>



<p>
</p><h1>Tareas</h1>

<p>
El trabajo se divide en dos partes:
</p><ol>
<li>Implementar tres políticas de ubicación de bloques.</li>
<li>Obtener rastros de ejecución de las llamadas <code>{malloc, realloc, free}</code> y mostrar la efectividad de cada una de las políticas.</li>
</ol>


<!---------------------------------------------------------------->
<h2>Tarea 1. Implementar tres políticas de ubicación</h2>

<p>
Implementar a partir de las estructuras de datos <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-memmgmnt/Bitmap.tar.gz"><tt>bitmap</tt></a> y <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-memmgmnt/Atable.tar.gz"><tt>atable</tt></a>, un heap manager que implemente las políticas:
</p><ul>
	<li>First Fit</li>
	<li>Best Fit</li>
	<li>Custom</li>
</ul>

<p>
Las 2 primeras se pueden encontrar en cualquier libro de texto.
<br>
La última deberá ser definida por ustedes <b>intentando mejorar las anteriores</b> (Random Fit, Elevator Fit, Wierd Fit, So So Fit, etc.).

</p><p>
La signatura de la biblioteca a definir <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-memmgmnt/HM.tar.gz"><tt>heapmanager.h</tt></a> está fija:

</p><ul>
<li>Constructor y destructor:
<pre width="150">// Constructor y destructor
// crea un HM a partir de un desplazamiento inicial, de un tamaño de memoria y bloque, que será administrado por una política
<a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *hm_create(void *const offset, const size_t mem_size, const size_t block_size, const policy_t policy);
void hm_destroy(<a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this);
</pre>

</li><li>Mutadores:
<pre width="125">// retorna la dirección asignada, NULL en caso de problemas
void *hm_malloc(<a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this, const size_t size);
// retorna la cantidad de memoria que tenía asignada
size_t hm_free(<a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this, void *const vtag);
</pre>

</li><li>Proyectores:
<pre width="125">void *hm_offset(const <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this);
size_t hm_mem_size(const <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this);
size_t hm_block_size(const <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this);
policy_t hm_policy(const <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this);
// retorna la cantidad de memoria libre
size_t hm_mem_free(const <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_s *this);
</pre>

</li></ul>

<p>
Este administrador de memoria <b>no manipula memoria real</b> solo va a llevar la cuenta de los bloques de memoria ocupados y los libres.


<!---------------------------------------------------------------->
</p><h3>Arquitectura del Driver</h3>


<table cellspacing="10">
<tbody><tr valign="top">
<td>
<p>
La biblioteca que ustedes programarán será <b>ejercitada</b> por un <i>driver</i> que nosotros damos <tt><a href="http://educa.di.unc.edu.ar/file.php/142/Lab-memmgmnt/HM.tar.gz">memdriver_test.c</a></tt>.
<br>
Las tareas de este driver son:
</p><ul>
	<li>Llamar a <tt>hm_malloc</tt> y <tt>hm_free</tt> con un rastro (trace) de las llamadas a <tt>malloc</tt> y <tt>free</tt> codificadas en un archivo de texto plano.
	</li><li>Transformar los rastros de <tt>realloc</tt> en <tt>free</tt>+<tt>malloc</tt>.
	</li><li>Comprobar la corrección de la implementación del <code><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>.c</code> llevando una contabilidad paralela de la memoria ocupada.
	</li><li>Dar información estadística a fin de medir la eficiencia de las políticas.
</li></ul>
El <b>diagrama de módulos</b> muestra en contexto el único módulo que tienen que codificar <code><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a></code>, asi como la estructura interna del memory driver.
<br>
El módulo <code>memdriver</code> utiliza los módulos <code>vr_extents</code> para llevar un registro paralelo de los segmentos contiguos de memoria ocupada y <code>mem_op</code> que empaqueta una operación de memoria.
Además está el módulo que ustedes deberán construir que a su vez hará uso de <code><a class="autolink" title="Atable" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3330">ATable</a></code> y <code><a class="autolink" title="Bitmap" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3331">Bitmap</a></code>.
<br>
El módulo principal <code>memdriver_test</code>, se encarga de
parsear las opciones de línea de comandos y a partir de un archivo de
entrada, parsea los datos y ejercita las cada una de las políticas,
además de recopilar y mostrar información complementaria a la que
brinda <code>memdriver</code>.
</td>
<td>
<img src="lab-memmgmnt_archivos/memmgmnt_mods.png" alt="Diagrama de módulos">
</td>
</tr>
</tbody></table>



<!--............................................................-->
<h3>Llamadas con trazas reales de ejecución</h3>

<p>
Utilizando la herramienta <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-memmgmnt/mtrace-dl.tar.gz"><tt>mtrace-dl</tt></a>, obtuvimos el rastro de ejecución de una sesión de <a href="http://links.sourceforge.net/">Links</a> un navegador modo texto.
En el archivo <a href="http://educa.di.unc.edu.ar/file.php/142/Lab-memmgmnt/trace-links.bz2"><tt>trace-links.bz2</tt></a> están todas las llamadas a <tt>malloc</tt>, <tt>realloc</tt> y <tt>free</tt>.
<br>
Las primeras 12 líneas son las siguientes:

</p><pre width="50">Mtrace version: dead0002
Initial brk: 8126000
start    Thu Oct 19 07:18:04 2006
malloc   0x8126008       88
free     0x8126008
malloc   0x8126008       38
realloc  0x8126008       39 0x8126008
malloc   0x8126038       39
realloc  0x8126038       45 0x8126038
realloc  0x8126038       46 0x8126038
free     0x8126008
malloc   0x8126008       44
</pre>

<p>
La primera columna indica el tipo de llamada.
<br>
En el caso de <tt>malloc</tt>, la segunda columna tiene la
dirección de memoria devuelta por el HM que utilizó este programa, y la
tercera el tamaño en bytes de la llamada.
<br>
El caso de <tt>realloc</tt> tenemos dirección antigua, nuevo tamaño y nueva dirección.
<br>
Para el <tt>free</tt> la segunda columna es el parámetro que indica que zona de memoria liberar.

</p><p>
Notar que las direcciones asignadas tienen que ver con la implementación del HM utilizado.
En este caso fue seguramente alguna implementación de <tt>malloc</tt> de la <tt>glibc</tt>, pero claramente podría haber sido cualquier otro, porque la <tt>glibc</tt> no es la única biblioteca/implentación que puede ser usada para pedir y liberar memoria.
<br>
Por ejemplo <a href="http://uclibc.org/">uClibc</a> es una libc para embedded devices y en el artículo de <a href="http://www.usenix.org/">USENIX</a>, "<i><a href="http://www.usenix.org/events/usenix01/freenix01/full_papers/bohra/bohra_html/node8.html">Are Mallocs Free of Fragmentation?</a></i>" se comparan varias implementaciones de <tt>malloc</tt>.
También tenemos que pensar que no todos los kernels administran el DS de la misma forma.

</p><p>
Las direcciones de memoria retornadas por <tt>malloc</tt> se suelen denominar <i>tags</i>, y dividimos estos tags en:
</p><ul>
	<li><b>real tags</b>: dados por la traza real que toma el programa.
	</li><li><b>virtual tags</b>: dado por la implementación del <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a> "virtual" que están realizando.
</li></ul>

<p>
Estas trazas ejercitarán las políticas con casos reales de uso.

<!--............................................................-->
</p><h3>Corrección</h3>

<p>El driver mantiene una "contabilidad paralela" de los bloques libres
y en uso, así como del mapeo entre la dirección de memoria de la traza,
o sea la devuelta por la glibc <tt>rtag</tt>, con la dirección que devuelve su biblioteca <tt>vtag</tt>.
</p><p>
Para ejemplificar esto último, la primera línea de la traza indica que el Links hizo un <tt>malloc(88)</tt> y la <tt>libc</tt> devolvió un <tt>void *</tt> apuntando a la dirección hexadecimal <tt>0x8126008</tt>.
<br>
A partir de esta línea el driver llama a <tt>hm_malloc(88)</tt> que devuelve por ejemplo el vtag <tt>0xFF</tt>, entonces se guarda el mapeo <i>(0x8126008 &lt;-&gt; 0xFF) -&gt; 88</i>, para que cuando llegue la 2da línea <tt>free 0x8126008</tt>, el driver invoque a <tt>hm_free(0xFF)</tt>.
</p><p>
También se verifica que no se asigne 2 veces un mismo bloque de memoria, o sea inconsistencias en la implementación.
(en realidad se chequean inconsistencias tanto en la traza real, como en la virtual).
<br>
Con esto evitamos las implementaciones "triviales", como por ejemplo devolver siempre la misma dirección de memoria en los <tt>hm_malloc</tt>.


<!--............................................................-->
</p><h3>Medición de parámetros</h3>

<p>
El driver concluye cuando la traza se acaba o bien cuando se llama a <tt>hm_malloc</tt> y este devuelve <tt>NULL</tt> indicando algún problema como por ejemplo que no había un bloque libre lo suficientemente grande.
<br><b>Notar entonces que las direcciones virtuales serán a partir de un <tt>offset</tt> o desplazamiento mayor estricto a 0</b>.

</p><p>
Al terminar se calcula:

</p><ul>
	<li>Porcentaje de traza recorrida.</li>
	<li>Cantidad de <tt>malloc</tt> y <tt>free</tt>.</li>
	<li>Promedio y máximo del tamaño de <tt>malloc</tt>, para saber si el <code>block_size</code> es correcto.</li>
	<li>Promedio y máximo del número de huecos, para medir parámetros de <b>fragmentación externa</b>.</li>
	<li>Promedio y máximo del tamaño promedio de huecos, también para medir fragmentación externa.
	</li>
	<li>Promedio y máximo de <b>fragmentación interna</b>, donde:<br>
		<center><table align="center" border="0"><tbody><tr><td>
		<table align="left"><tbody><tr><td align="center" nowrap="nowrap">
		fragmentación interna = 1 - </td>
		<td align="center" nowrap="nowrap">
		memoria pedida por la aplicación<hr noshade="noshade">
		memoria usada por el sistema<br></td><td align="center" nowrap="nowrap">
		</td></tr></tbody></table>
		</td></tr></tbody></table></center>
	</li>
	<!--
	<%10.12%>Sobrecarga de memoria de la implementación.
		<br><b>?Como carajos medirla, porque una cosa es en vacío y otra es cuando la hash esta llenita.</b>
	</li>
	-->
</ul>

<!--
<%13.21%>
Notar que si la traza es completa, el proceso original no tiene memory leaks, y ningún <tt>hm_malloc</tt> falla, la mayoría de estas mediciones no informarán nada.
-->
<p>
Es de esperar que una buena política de ubicación logre pocos
fragmentos libres y de tamaño grande, así como un buen porcentaje de la
traza recorrida.
<!--............................................................-->
</p><h3>Implementación dummy</h3>

<p>
Se entrega una implementación de prueba <tt><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_dummy.{h,c}</tt> donde se supone que hay infinita cantidad de memoria, la cual se va asignando siempre adelante (notar que hay un <i>symlink</i>, <code><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>.c -&gt; <a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_dummy.c</code>.). 
<br>
A manera de ejemplo, podemos correr la traza del navegador Links <code>test04.mt</code> sobre esta implementación.

</p><pre width="100">nicolasw@negra:~/sistop/trunk/Lab-memmgmnt/HM$ ./memdriver_test test04.mt 24 24
mem_size: 16777216, policy: 0
        porcentaje de rastro: 71216/71216 (100.00%)
        cuenta de malloc: 38563, free: 38554, total: 77117
        promedio y máximo de tamaño malloc: 391, 105298
        promedio y máximo número de huecos: 866, 1761
        promedio y máximo del tamaño promedio de huecos: 65807, 16777216
        promedio y máximo de fragmentación interna: 0.00, 0.70
mem_size: 16777216, policy: 1
        porcentaje de rastro: 71216/71216 (100.00%)
        cuenta de malloc: 38563, free: 38554, total: 77117
        promedio y máximo de tamaño malloc: 391, 105298
        promedio y máximo número de huecos: 866, 1761
        promedio y máximo del tamaño promedio de huecos: 65807, 16777216
        promedio y máximo de fragmentación interna: 0.00, 0.70
mem_size: 16777216, policy: 2
        porcentaje de rastro: 71216/71216 (100.00%)
        cuenta de malloc: 38563, free: 38554, total: 77117
        promedio y máximo de tamaño malloc: 391, 105298
        promedio y máximo número de huecos: 866, 1761
        promedio y máximo del tamaño promedio de huecos: 65807, 16777216
        promedio y máximo de fragmentación interna: 0.00, 0.70
</pre>

<p>
Notamos:
</p><ul>
	<li>Las tres políticas con iguales en la implementación dummy.</li>
	<li>Se llama al driver para que realice el test sólo para 16MB = 2<sup>24</sup>B = <code>(1&lt;&lt;24)</code>B.</li>
	<li>Se cubre el 100% del rastro.</li>
	<li>Por los realloc, la cuenta de malloc y free que llegan al <code><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>_dummy</code> es mayor a la cantidad de entradas en el rastro.</li>
	<li>En general el tamaño de los malloc es pequeño.</li>
	<li>El máximo del tamaño promedio de huecos es el total de la memoria, o sea no sirve para nada.</li>
	<li>La fragmentación interna en promedio, es baja, debido a que el <code>BLOCK_SIZE = 128</code> es pequeño.</li>
</ul>


<!---------------------------------------------------------------->
<h2>Tarea 2: Obtener rastros de ejecución y mostrar la efectividad de cada una de las políticas</h2>

<p>Una vez implementadas las políticas deberán obtener trazas y
aplicarlas a las tres políticas en diferentes tamaños de memoria para
mostrar:
</p><ol>
	<li>Que la política <code>Custom</code> es en general mejor que las otras dos para trazas de aplicaciones reales .</li>
	<li>Que no existe la mejor política.</li>
</ol>

<p>
Para el primer punto hay que extraer varias trazas (media docena está bien) y mostrar que en la mayoría de ellas <code>Custom</code> logra mayor porcentaje de ejecución de trazas.
</p><p>
Para el segundo hay que obtener 3 trazas de <b>reales</b> o <b>sintéticas</b> (hechas a mano) <code>{firstfit_best.mt, bestfit_best.mt, custom_best.mt}</code> donde para una cantidad fija de memoria en cada una <code>{m1, m2, m3}</code>:
</p><ol>
	<li>La política <code>FirstFit</code> llegue más lejos en <code>./memdriver_test firstfit_best.mt m1 m1</code>.</li>
	<li>La política <code>BestFit</code> llegue más lejos en <code>./memdriver_test bestfit_best.mt m2 m2</code>.</li>
	<li>La política <code>Custom</code> llegue más lejos en <code>./memdriver_test custom_best.mt m3 m3</code>.</li>
</ol>


<!--============================================================-->
<h1>Como atacar el problema</h1>

<p>
Se recomienda implementar la política más sencilla <tt>FirstFit</tt> primero y comprobar que el driver no muestra problemas.

</p><p>
Se pueden hacer los siguientes tests que muestran que las políticas están funcionando de manera esperable:

</p><ul>
	<li>A mayor cantidad de <tt>mem_size</tt>, mayor porcentaje de traza debería ser completada para <i>cualquier</i> política.</li>
	<li>La fragmentación interna es independiente de la política y está directamente relacionada con <tt>BLOCK_SIZE</tt>.</li>
	<li>Podemos bajar todo lo que querramos la fragmentación interna haciendo más pequeño <tt>BLOCK_SIZE</tt>, pero la sobrecarga introducida por las estructuras de datos será muy grande.</li>
</ul>


<!--============================================================-->
<h1>Qué se debe Entregar</h1>
<ul>
	<li>Implementación del <tt><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a>.{h,c}</tt> que no provoque excepciones en el driver que se les entrega, testeado en un número considerable de trazas.</li>
	<li>Trazas
relacionadas al punto 2, tanto para mostrar que la política Custom es
mejor en general, como para mostrar la incomparabilidad de las
políticas </li><li>Documentación, incluyendo la justificación de la política Custom.</li>
</ul>


<!--============================================================-->
<h1>Ayudas</h1>
<ul>
	<li>Pensar los algoritmos de ubicación sobre <a class="autolink" title="Ejemplos" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3117">ejemplos</a> en papel.</li>
	<li>Pensar siempre en bloques de tamaño <i>2<sup>n</sup></i>, de paso se puede almacenar solo el <i>n</i> y hacer todas las cuentas con aritmética binaria (<tt>&gt;&gt;, &lt;&lt;, &amp;, |</tt>).</li>
	<li>El tamaño de memoria debería ser un múltiplo del tamaño de bloque.</li>
</ul>


<!--============================================================-->
<p>
</p><h1>Tareas Adicionales</h1>

<p>
Si les sobra tiempo pueden hacer las siguientes mejoras:
</p><ul>
	<li>Implementar el realloc en el <code><a class="autolink" title="HeapManager" href="http://educa.di.unc.edu.ar/mod/resource/view.php?id=3332">heapmanager</a></code> y modificar <code>memdriver</code> para que no se haga la interpretación de los realloc como free+malloc.</li>
	<li>Reimplementar el lazo principal para hacer <i>búsqueda binaria</i> de la menor cantidad de memoria que una política dada necesita para llegar al 100% de una traza.
	<br>Con esto podemos medir la efectividad de la política en términos más concretos.
	</li>
	<li>Mostrar
que para todas las trazas involucradas, y para todas las políticas,
siempre existe un tamaño de memoria tal que se llega al 100% de la
traza.</li>
</ul>

<!-- Footer -->
<div align="right"> <br>
	<font size="-1">
	$Date: 2007-10-24 17:27:06 -0300 (Wed, 24 Oct 2007) $,
	$Revision: 179 $
	</font>
</div>


</body></html>